GATE CSE 2001
Q21.
Consider a schema R(A,B,C,D) and functional dependencies A\rightarrowB and C\rightarrowD. Then the decomposition of R into R1(AB) and R2(CD) is :Q22.
Consider the following relations: R1(a,b) iff (a+b) is even over the set of integers R2(a,b) iff (a+b) is odd over the set of integers R3(a,b) iff a.b > 0 over the set of non-zero rational numbers R4(a,b) iff |a - b| <= 2 over the set of natural numbers Which of the following statements is correct?Q23.
Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort ?Q24.
The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned addresses is calledQ25.
Consider the undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r . Let d(r,u) and d(r,v) be the lengths of the shortest paths form r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct ?Q26.
Consider the following problem x . Given a Turing machine M over the input alphabet \Sigma, any state q of M. And a word w \in \Sigma *) does the computation of M on w visit the state q ? Which of the following statements about x is correct ?Q28.
Consider the circuit given below the initial state Q_{0}=1, Q_{1}=Q_{2}=0. The state of the circuit is given by the value 4Q_{2}+2Q_{1}+Q_{0} Which one of the following is the correct state sequence of the circuit ?Q29.
Consider the following circuit with initial state Q0 = Q1 = 0. The D flip-flops are positive edged triggered and have set up times 20 nanosecond and hold times 0.